ABC147 D Xor Sum 4
次のようにして解くことができる.
各桁ごとに分割して考える
.
すると登場する数は
$ 0, 1
のみであるから, 次のように場合分けすることで今(末尾から0-indexedで)
$ i
桁目であるとすると答えが
$ 2^i \cdot (0の個数) \cdot (1の個数)
であることを導ける.
$ 0, 0
もしくは
$ 1, 1
の場合, 加算されるのは
$ 0
(打ち消される)
$ 0, 1
もしくは
$ 1, 0
の場合, 加算されるのは
$ 2^i
よってこの問題を高速に解くことができた.